#include <stdio.h>

#include "bitree.h"

BiTree maxNode;

void UpdateMaxNode(BiTree t) {
    if (t->data > maxNode->data) {
        maxNode = t;
    }
}

void PreOrderUpdate(BiTree t) {
    if (!t) return;
    UpdateMaxNode(t);
    PreOrderUpdate(t->lchild);
    PreOrderUpdate(t->rchild);
}

void InOrderUpdate(BiTree t) {
    if (!t) return;
    InOrderUpdate(t->lchild);
    UpdateMaxNode(t);
    InOrderUpdate(t->rchild);
}

void PostOrderUpdate(BiTree t) {
    if (!t) return;
    PostOrderUpdate(t->lchild);
    PostOrderUpdate(t->rchild);
    UpdateMaxNode(t);
}

void LevelOrderUpdate(BiTree t) {
    if (!t) return;
    SqQueue q;
    InitQueue(&q);
    EnQueue(&q, t);
    while (!QueueEmpty(&q)) {
        BiTree p;
        DeQueue(&q, (void**)&p);
        if (p) {
            UpdateMaxNode(p);
            EnQueue(&q, p->lchild);
            EnQueue(&q, p->rchild);
        }
    }
}

void TestFindMaxNode(BiTree t) {
    printf("test begin\n");

    struct {
        char* name;
        void (*update)(BiTree);
    } testFunc[] = {{"先序遍历", PreOrderUpdate},
                    {"中序遍历", InOrderUpdate},
                    {"后序遍历", PostOrderUpdate},
                    {"层序遍历", LevelOrderUpdate}};

    for (int i = 0; i < sizeof(testFunc) / sizeof(testFunc[0]); ++i) {
        maxNode = t;
        printf("%s: ", testFunc[i].name);
        testFunc[i].update(t);
        if (maxNode) {
            printf("最大值为: %c\n", maxNode->data);
        } else {
            printf("找不到最大值\n");
        }
    }

    printf("test end\n");
}

int main() {
    ElemType arr1[] = {'A'};
    BiTree t1;
    LevelOrderCreateBiTree(&t1, arr1, 1);
    TestFindMaxNode(t1);

    ElemType arr2[] = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
    BiTree t2;
    LevelOrderCreateBiTree(&t2, arr2, 7);
    TestFindMaxNode(t2);

    return 0;
}